/*********************************************************************************
 * Software License Agreement (BSD License)
 * Copyright (c) 2012, Carlos D. Correa (info@ngraph.org)
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 * 
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of netzen nor the
 *    names of its contributors may be used to endorse or promote products
 *    derived from this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 *  LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *********************************************************************************/
#include "graph.h"
#include "controller.h"
#include <assert.h>
#include <math.h>

Graph::Graph(Controller *controller): Object("Graph","UnnamedGraph") {
	this->controller = controller;
	numEdges = 0;
}
Graph::Graph(const char *name, Controller* controller): Object("Graph",name) {
	this->controller = controller;
	numEdges = 0;
}
Graph::~Graph() {
  //print("Deleting Graph\n");
  for(unsigned int i=0;i<nodes.size();i++) {
    delete nodes[i];
  }
}

void Graph::clear() {
	nodes.clear();
	nodeMap.clear();
	numEdges = 0;
}

StatManager *Graph::getStatManager() {
  return stats;
}
void Graph::setStatManager(StatManager *s) {
  stats = s;
}

void Graph::createNodes(int startId, int endId) {
  for(int i=startId; i<=endId;i++) {
    char str[20];
    sprintf(str, "%d", i);
    addNode(str);
  } 
}


Node *Graph::addNode(Node *n) {
	int id = atoi(n->getName().c_str());
    nodes.push_back(n);	
    nodeMap[id] = n; 
	return n;
}

// To do: change nodeid for string
Node * Graph::addNode(const char *name) {
  int id = atoi(name); // name: serial string id for node according to read-in sequence of nodes.
  Node *n = nodeMap[id];
  if(!n) {
    n = new Node(name); 
    n->setIndex(nodes.size()); //nodeIndex: the index of the node in the graph.
    nodes.push_back(n);

    nodeMap[id] = n; // map from read-in "NodeId" to the node.
    //print("Added node [%s]--[%d] %d\n", name, id, nodes.size());
  }
  return n;
}

// Here, from and to are Identifiers, not Indices
Edge * Graph::addEdge(int from, int to) {
  //assert(to>=0 && to<(int) nodes.size());
  //assert(from>=0 && from<(int) nodes.size());
  Node *n1, *n2;
  n1 = 0;
  n2 = 0;

  n1 = nodeMap[from];
  n2 = nodeMap[to];

  // to do:
  // if any of the nodes is null, add a new Node
  if(!n1) {
    char id[20];
    sprintf(id, "%d", from); 
    n1 = addNode(id);
  }
  if(!n2) {
    char id[20];
    sprintf(id, "%d", to); 
    n2 = addNode(id);
  }

  //print("Added edge %d %d -- %d %d\n", to, from, n1->getIndex(), n2->getIndex());

  if(!n1 && !n2 && from<(int) nodes.size() && to<(int) nodes.size()) {
    //n1 = nodes[from];
    //n2 = nodes[to];
  }
  if(n1!=0 && n2!=0) {
    //print("Added edge %d %d\n", to, from);
		numEdges++;
    return n1->addEdge(n2);
  } 
  return 0;
  
}

void Graph::computeNodeMinMaxFloat(string name) {
    float minv, maxv;
    float minNeg, maxNeg;
    float minPos, maxPos;
		minPos = 1e20;	maxPos = -1.0;
		minNeg = 1.0; 1e20; maxNeg = -1e20;
    minv = maxv = 0;
    float sumx = 0, sumx2 = 0, sumn = 0;
    for(unsigned int i=0;i<nodes.size();i++) {
        float v = nodes[i]->getPropertyFloat(name);
        sumx+=v;
        sumx2+=v*v;
        sumn+=1.0;
        if(i==0 && (v<0 || v>0)) {
            minv = maxv = v;
            if(v<0) minNeg = maxNeg = v;
            if(v>0) minPos = maxPos = v;
        }
        minv = fmin(minv, v);
        maxv = fmax(maxv, v);
        if(v<0) {
            minNeg = fmin(minNeg, v);
            maxNeg = fmax(maxNeg, v);
        } else if(v>0) {
            minPos = fmin(minPos, v);
            maxPos = fmax(maxPos, v);
        }
    }
    float mean = (sumn>0)? sumx/sumn:0.0;
    float var = (sumn>0)? sumx2/sumn - mean*mean: 0.0;
    float stdev = (sumn>1)? sqrt(sumn/(sumn-1))*sqrt(fabs(var)) : 0.0;
    stats->setMinMaxFloat(name, minv, maxv);
    stats->setMinMaxFloatNeg(name, minNeg, maxNeg);
    stats->setMinMaxFloatPos(name, minPos, maxPos);
    stats->setMean(name, mean);
    stats->setStandardDeviation(name, stdev);		

}
void Graph::computeNodeMinMaxInt(string name){
    float minv, maxv;
    float minNeg, maxNeg;
    float minPos, maxPos;
    minPos = maxPos = 0;
    minNeg = maxNeg = 0;
    minv = maxv = 0;
    for(unsigned int i=0;i<nodes.size();i++) {
      float v = (float)nodes[i]->getPropertyInt(name);
      if(i==0) {
        minv = maxv = v;
        if(v<0) minNeg = maxNeg = v;
        if(v>0) minPos = maxPos = v;
      }
      minv = fmin(minv, v);
      maxv = fmax(maxv, v);
      if(v<0) {
        minNeg = fmin(minNeg, v);
        maxNeg = fmax(maxNeg, v);
      } else {
        minPos = fmin(minPos, v);
        maxPos = fmax(maxPos, v);
      }
    }
    stats->setMinMaxFloat(name, minv, maxv);
    stats->setMinMaxFloatNeg(name, minNeg, maxNeg);
    stats->setMinMaxFloatPos(name, minPos, maxPos);

}

void Graph::computeEdgeMinMaxFloat(string name) {
  float minv, maxv;
  float minNeg, maxNeg;
  float minPos, maxPos;
  minPos = maxPos = 0;
  minNeg = maxNeg = 0;
  minv = maxv = 0;
	float sumx = 0, sumx2 = 0, sumn = 0;
  for(unsigned int i=0;i<nodes.size();i++) {
    Node  *node = nodes[i];
    for(unsigned int k=0;k<node->edges.size();k++) {
				float v = node->edges[k]->getPropertyFloat(name);
				sumx+=v;
				sumx2+=v*v;
				sumn+=1.0;
				if(i==0 && k==0) {
					minv = maxv = v;
					if(v<0) minNeg = maxNeg = v;
					if(v>0) minPos = maxPos = v;
				}
				minv = fmin(minv, v);
				maxv = fmax(maxv, v);
				if(v<0) {
					minNeg = fmin(minNeg, v);
					maxNeg = fmax(maxNeg, v);
				} else if(v>0) {
					minPos = fmin(minPos, v);
					maxPos = fmax(maxPos, v);
				}
      }
  }
	float mean = (sumn>0)? sumx/sumn:0.0;
	float var = (sumn>0)? sumx2/sumn - mean*mean: 0.0;
	float stdev = (sumn>1)? sqrt(sumn/(sumn-1))*sqrt(fabs(var)) : 0.0;
  stats->setMinMaxFloat(name, minv, maxv);
  stats->setMinMaxFloatNeg(name, minNeg, maxNeg);
  stats->setMinMaxFloatPos(name, minPos, maxPos);
	stats->setMean(name, mean);
	stats->setStandardDeviation(name, stdev);		
}
void Graph::computeEdgeMinMaxInt(string name) {
  float minv, maxv;
  float minNeg, maxNeg;
  float minPos, maxPos;
  minPos = maxPos = 0;
  minNeg = maxNeg = 0;
  minv = maxv = 0;
  for(unsigned int i=0;i<nodes.size();i++) {
    Node  *node = nodes[i];
    for(unsigned int k=0;k<node->edges.size();k++) {
        float v = (float)node->edges[k]->getPropertyInt(name);
				if(i==0 && k==0) {
          minv = maxv = v;
          if(v<0) minNeg = maxNeg = v;
          if(v>0) minPos = maxPos = v;
        }
        minv = fmin(minv, v);
        maxv = fmax(maxv, v);
        if(v<0) {
          minNeg = fmin(minNeg, v);
          maxNeg = fmax(maxNeg, v);
        } else {
          minPos = fmin(minPos, v);
          maxPos = fmax(maxPos, v);
        }
      }
  }
  stats->setMinMaxFloat(name, minv, maxv);
  stats->setMinMaxFloatNeg(name, minNeg, maxNeg);
  stats->setMinMaxFloatPos(name, minPos, maxPos);
}
void Graph::computeEdgeMinMaxBool(string name) {
  float minv, maxv;
  float minNeg, maxNeg;
  float minPos, maxPos;
  minPos = maxPos = 0;
  minNeg = maxNeg = 0;
  minv = maxv = 0;
  for(unsigned int i=0;i<nodes.size();i++) {
      Node  *node = nodes[i];
      for(unsigned int k=0;k<node->edges.size();k++) {
          //        Edge *eg = node->edges[k];
          //        bool bv = eg->getPropertyBool(name,true);
          bool bv = (node->edges[k])->getPropertyBool(name,false);
          float v=0.0;// = node->edges[k]->getPropertyFloat(name);
          if(bv==true){
              v = 1.0;
          }
          else if (bv==false){
              v = 0.0;
          }

          if(i==0 && k==0) {
              minv = maxv = v;
              if(v<0) minNeg = maxNeg = v;
              if(v>0) minPos = maxPos = v;
          }
          minv = fmin(minv, v);
          maxv = fmax(maxv, v);
          if(v<0) {
              minNeg = fmin(minNeg, v);
              maxNeg = fmax(maxNeg, v);
          } else {
              minPos = fmin(minPos, v);
              maxPos = fmax(maxPos, v);
          }
      }
  }
  stats->setMinMaxFloat(name, minv, maxv);
  stats->setMinMaxFloatNeg(name, minNeg, maxNeg);
  stats->setMinMaxFloatPos(name, minPos, maxPos);
}

void Graph::computeImplicitEdgeMinMaxFloat(string name) {
  float minv, maxv;
  minv = maxv = 0;
  for(unsigned int i=0;i<nodes.size();i++) {
    Node  *node = nodes[i];
    for(unsigned int k=0;k<nodes.size();k++) {
      if(!node->hasEdge(k)) continue;
	float v = node->getImplicitEdge(k)->getPropertyFloat(name);
	if(i==0 && k==0) {
	  minv = maxv = v;
	}
	minv = fmin(minv, v);
	maxv = fmax(maxv, v);
      }
  }
  stats->setMinMaxFloat(name, minv, maxv);
}


/**
 * Iterators
 */

NodeIterator::NodeIterator(Graph *g):ElementIterator() {
	idx = 0;
	graph = g;
	N = (int) graph->nodes.size();
}
void NodeIterator::begin() {
	idx = 0;
}
bool NodeIterator::hasMoreElements() {
	return (idx < N);
}
PropertyBag *NodeIterator::next() {
	PropertyBag* el = graph->nodes[idx];
	idx++;
	return el;
}

EdgeIterator::EdgeIterator(Graph *g):ElementIterator() {
	idx = 0;
	idxEdge = 0;
	graph = g;
	N = (int) graph->nodes.size();
}
void EdgeIterator::begin() {
	idx = 0;
	idxEdge = 0;
}

bool EdgeIterator::hasMoreElements() {
	return (idx < N) && (idxEdge<(int) graph->nodes[idx]->edges.size());
}
PropertyBag *EdgeIterator::next() {
	PropertyBag* el = graph->nodes[idx]->edges[idxEdge];
	idxEdge++;
	if(idxEdge>=(int) graph->nodes[idx]->edges.size()) {
		idx++;
		idxEdge = 0;
	}
	return el;
}


NeighborIterator::NeighborIterator(Graph *g, Node *n):NodeIterator(g) {
	node = n;
}
void NeighborIterator::begin() {
	assert(node);
	idx = 0;
}
bool NeighborIterator::hasMoreElements() {
	return (idx<(int) node->edges.size());
}
PropertyBag *NeighborIterator::next() {
	PropertyBag* el = node->edges[idx]->getNode1();
	idx++;
	return el;
}


IncidentEdgeIterator::IncidentEdgeIterator(Graph *g, Node *n):EdgeIterator(g) {
	node = n;
}
void IncidentEdgeIterator::begin() {
	assert(node);
	idx = 0;
}
bool IncidentEdgeIterator::hasMoreElements() {
	return (idx<(int) node->edges.size());
}
PropertyBag *IncidentEdgeIterator::next() {
	PropertyBag* el = node->edges[idx];
	idx++;
	return el;
}

/**
 * Properties
 */


float Graph::getAsFloat(PropertyBag *bag, string property, float defaultValue, bool normalized) {
    assert(bag);
	assert(controller);
	
    float value = defaultValue;
    if(!bag->hasProperty(property) || property=="Default") return defaultValue;
    int type = bag->getPropertyType(property);
    float minv, maxv;
    minv = 0, maxv = 1.0;
    if(type==PROPERTY_FLOAT || type==PROPERTY_SIGNED) {
        value = bag->getPropertyFloat(property);
        this->getStatManager()->getMinMaxFloat(property, minv, maxv);
    } else if(type==PROPERTY_INT) {
        value = (float) bag->getPropertyInt(property);
        this->getStatManager()->getMinMaxFloat(property, minv, maxv);
    } else if(type==PROPERTY_BOOL) {
        value = bag->getPropertyBool(property)? 1.0f:0.0f;
        maxv = 1.0; minv = 0.0;
    } else if(type==PROPERTY_STRING || type==PROPERTY_ORDINAL) {
        value = 0.0 + (float) controller->stringToInt(property,bag->getPropertyString(property));
        minv = 0;
        maxv = (float) controller->numStringValues(property)-1;
    }
		//printf("Getting property [%s] type = %d as float: %f minmax=%f %f\n", property.c_str(), type, value, minv, maxv);
    return (normalized && fabs(maxv-minv)>0)? (value-minv)/(maxv-minv) : value;
}

float Graph::getAsNormalizedFloat(PropertyBag *bag, string property, float defaultValue) {
	return getAsFloat(bag, property, defaultValue, true);
}

/**
 * Get data property as a integer
 */
int Graph::getAsInteger(PropertyBag *bag, string property, int defaultValue) {
    assert(controller);
    assert(bag);
	
    int value = defaultValue;
    if(!bag->hasProperty(property) || property=="Default") return defaultValue;
    int type = bag->getPropertyType(property);
    if(type==PROPERTY_FLOAT || type==PROPERTY_SIGNED) {
        value = (int) (bag->getPropertyFloat(property));
    } else if(type==PROPERTY_INT) {
        value = bag->getPropertyInt(property);
    } else if(type==PROPERTY_BOOL) {
        value = bag->getPropertyBool(property)? 1:0;
    } else if(type==PROPERTY_STRING || type==PROPERTY_ORDINAL) {
        value = controller->stringToInt(property,bag->getPropertyString(property));
    }
    return value;
}

/**
 * Get data property as a boolean
 */
bool Graph::getAsBoolean(PropertyBag *bag, string property) {
    assert(controller);
    assert(bag);
	
    bool value = true;
    if(!bag->hasProperty(property) || property=="Default") return true;
    int type = bag->getPropertyType(property);
    if(type==PROPERTY_FLOAT || type==PROPERTY_SIGNED) {
        value = (int) (bag->getPropertyFloat(property)) > 0;
    } else if(type==PROPERTY_INT) {
        value = bag->getPropertyInt(property) > 0;
    } else if(type==PROPERTY_BOOL) {
        value = bag->getPropertyBool(property);
    } else if(type==PROPERTY_STRING || type==PROPERTY_ORDINAL) {
        value = bag->getPropertyString(property)=="true";
    }
    return value;
}


float Graph::getAsSigned(PropertyBag *bag, string property, float defaultValue, bool /*normalized*/) {
    assert(controller);
	assert(bag);
	
    float value = defaultValue;
    if(!bag->hasProperty(property) || property=="Default") return defaultValue;
    float minv, maxv;
    minv = 0, maxv = 1.0;
	
    this->getStatManager()->getMinMaxFloat(property, minv, maxv);
    value = getAsFloat(bag, property, defaultValue, false);
    float maxAbs = fmax(fabs(minv), fabs(maxv));
    if(value<0) {
        value= fabs(value)/-maxAbs;
    } else {
        value = fabs(value)/maxAbs;
    }
    return value;
}

string Graph::getAsString(PropertyBag *bag, string property, string defaultValue, bool /*normalized*/) {
    assert(bag);
    int type = bag->getPropertyType(property);
    float minv, maxv;
    minv = 0, maxv = 1.0;
    char str[200];
    string stringValue = defaultValue;
    if(type==PROPERTY_FLOAT || type==PROPERTY_SIGNED) {
        float value = bag->getPropertyFloat(property);
        this->getStatManager()->getMinMaxFloat(property, minv, maxv);
        sprintf(str, "%.2f", value);
        stringValue = string(str);
    } else if(type==PROPERTY_INT) {
        int value = (int) bag->getPropertyInt(property);
        this->getStatManager()->getMinMaxFloat(property, minv, maxv);
        sprintf(str, "%d", value);
        stringValue = string(str);
    } else if(type==PROPERTY_BOOL) {
        bool value = bag->getPropertyBool(property)? 1.0f:0.0f;
        stringValue = (value)? "true":"false";
    } else if(type==PROPERTY_STRING || type==PROPERTY_ORDINAL) {
        stringValue = bag->getPropertyString(property);
    }
    return stringValue;
}

NodeIterator *Graph::createNodeIterator() {
	return new NodeIterator(this);
}
EdgeIterator *Graph::createEdgeIterator() {
	return new EdgeIterator(this);
}
NodeIterator *Graph::getNeighbors(int i) {
	return new NeighborIterator(this, nodes[i]);
}
EdgeIterator *Graph::getEdges(int i) {
	return new IncidentEdgeIterator(this, nodes[i]);
}
NodeIterator *Graph::getNeighbors(Node *node) {
	return new NeighborIterator(this, node);
}
EdgeIterator *Graph::getEdges(Node *node) {
	return new IncidentEdgeIterator(this, node);
}
void Graph::destroyIterator(ElementIterator *it) {
	delete it;
}
